{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "$\\Sigma$ Protocols\n", "================" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Definitions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "let $R$ be a binary relation, i.e., $R$ is a subset of $\\{0, 1\\}^∗ \\times \\{0, 1\\}^∗$ , where the only restriction is that if $(x, w) ∈ R$, then the length of $w$ is at most $p(|x|)$, for some polynomial $p()$. \n", "\n", "For some $(x, w) ∈ R$, we may think of $x$ as an instance of some computational problem, and $w$ as the solution to that instance. We call $w$ a witness for $x$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will be concerned with protocols of the following form, where $x$ is common input to $P, V$ and a w such that $(x, w)\\in R$ is private input to $P$:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. $P$ sends a message a.\n", "\n", "2. $V$ sends a random $t-bit$ sting $e$\n", "\n", "3. $P$ sendss reply $z$, and $V$ decides to accept or reject based on the data has be seen, i.e. $x, a, e,z$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will assume throughout that both $P, V$ are probabilistic polynomial time machines, so $P$’s only advantage over $V$ is that he knows $w$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Definition $\\Sigma$-protocol.\n", "\n", "A protocol $P$ is said to be a $\\Sigma$-protocol for relation $R$ if:\n", "\n", "- $P$ is of the above 3-move form, and we have completeness: if $P, V$ follow the protocol on input $x$ and private input $w$ to $P$ where $(x, w) ∈ R$, the verifier always accepts." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* From any $x$ and any pair of accepting conversations on input $x$, $(a,e,z),(a,e',z')$ where $e\\neq e'$, one can efficiently compute $w$ such that $(x,w)\\in R$. This is sometimes called the **special soundness property**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* There exists a polynomial-time simulator $M$, which on input $x$ and a random $e$ outputs an accepting conversation of the form $(a, e, z)$, with the same probability distribution as conversations between the honest $P, V$ on input $x$. This is sometimes called **special honest-verifier zero-nowledge (sHVZK)**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Define $L_R$ to be the set of $x’s$ for which there exist $w$ such that $(x, w) ∈ L$. Then the special soundness property implies that a $\\sigma$-protocol for $R$ is always an interactive proof system for $L_R$ with error probability $2^t$ ." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Lemma 1.\n", "\n", "The properties of $\\sigma$-protocols are invariant under parallel composition, for instance repeating a Σ-protocol for $R$ twice in parallel produces a new $Σ$-protocol for $R$ with challenge length $2t$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Lemma 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If a Σ-protocol for $R$ exists, then for any $t$, there exists a Σ-protocol for $R$ with challenge length $t$.\n", "\n", "* Proof.\n", "\n", "Let $t'$ be the challenge length for the given protocol $P$. Then any challenge length $t$ shorter than $t'$ can be implemented as follows: \n", "\n", "$P$ sends the first message a as in $P$. $V$ sends a random $t$-bit string $e$. \n", "\n", "$P$ appends $t' − t$ zeros to $e$, calls the result $e'$ and computes the answer $z$ to $e'$ as in $P$.\n", "\n", "$V$ checks $z$ as in $P$, as if the challenge was $e'$ .\n", "\n", "Any challenge length $t > t'$ can be implemented by first repeating the given protocol in parallel $j$ times, such that $jt' ≥ t$, and then possibly adjusting down to $t$ as above." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Definition Proofs of Knowledge" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let $κ()$ be a function from bit strings to the interval $[0..1]$. The protocol $(P, V)$ is said to be a proof of knowledge for the relation $R$ with knowledge error $κ$, if the following are satisfied:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Completeness\n", "\n", "On common input $x$, if the honest prover $P$ gets as private input $w$ such that $(x, w) ∈ R$, then the verifier $V$ always accepts.\n", "\n", "* Knowledge soundness\n", "\n", "There exists a probabilistic algorithm $M$ called the **knowledge extractor**. \n", "\n", "This $M$ gets input $x$ and rewindable black-box access to the prover and attempts to compute $w$ such that $(x, w) ∈ R$.\n", "\n", "We require that the following holds: For any prover $P∗$ , let $\\epsilon(x)$ be the probability that $V$ accepts on input $x$. There exists a constant $c$ such that whenever $\\epsilon(x) > κ(x)$, $M$ will output a correct $w$ in expected time at most\n", "\n", "$$\n", "\\frac{|x|}{\\epsilon(x)-k(x)}\n", "$$\n", "\n", "where access to $P∗$ counts as one step only." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Ref: \n", "\n", "* Ivan Damg˚ard, On Σ-protocols https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=2ahUKEwiO8qym9dLlAhXKl54KHdPIA9EQFjAAegQIBRAC&url=http%3A%2F%2Fwww.cs.au.dk%2F~ivan%2FSigma.pdf&usg=AOvVaw1Jw9tKPLGZViKm3xOjwnaC" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.2" } }, "nbformat": 4, "nbformat_minor": 2 }